# 感觉状压的题好难啊呜呜呜
W, n = map(int, input().split())
s, w = [0] * n, [0] * n
for i in range(n):
    s[i], w[i] = map(int, input().split())
dp = [1e5] * (1 << n) # 因为找最小值，所以dp初值设大一些。
for i in range(1<<n): # 遍历0 到 2^n - 1，他们中的1的位置和数量可以代表所有选择的可能
    ww, ss, j, l = 0, 0, i, 0 # ww是重量和，ss是最高损伤度，l是代表第几个小车
    while j: # j不为0就继续
        if j & 1: # 如果j的最后一位是1，就代表选择当前的小车
            if s[l] > ss: ss = s[l] # ss存最大的损伤度
            ww += w[l] # ww存重量和
            if ww > W: break # 如果重量大于最大承重了，直接break，毫不留情！
        l += 1 # 不管j的最后一位是不是1，l都要加1，这样才能统计出每种不同的情况
        j >>= 1 # j的二进制右移1位，比如(1010)2 -> (101)2 -> (10)2 -> (1)2 -> 0，每次l + 1，而只有最后一位为1才记录，是吧是吧，0到2^n - 1的二进制就包含了所有选或不选的可能！！！
    else: dp[i] = ss # 我之前好像写过while-else，就是结束while循环的之后，会执行else里的语句，不管是正常结束，还是break强制结束都可以。
for i in range(1<<n):
    j = i
    while j: # 这个遍历所有子集的方法，我也不太懂呢，先死记硬背一下吧。。
        dp[i] = min(dp[i], dp[j] + dp[j ^ i])
        j = (j - 1) & i
print(dp[-1])
# python果然超时了。。
# -------------------------------------------------------------------------------

# 比赛环境为python3.8.6版本自带的IDLE，最好早点熟悉一下。。这个东西的提示时有时无

# 菜单栏最右边的Help的Python Docs 比赛时候也可以看，不过建议还是提前多了解了解，

# 比赛的时候至少知道在文档找什么能用的上。

# IDLE是下载Python时自带的，在按住win+s搜索IDLE就能搜到了。

# 然后点左上角的File可以创建新文件，然后按F5可以运行。
